/*
二叉树遍历比较
DFS
void dfs(TreeNode* root) {
    if (root == nullptr) return;
    dfs(root->left);
    dfs(root->right);
}
BFS
void bfs(TreeNode* root) {
    std::queue<TreeNode*> queue;
    if (root != nullptr) queue.push(root);
    while(!queue.empty()) {
        TreeNode* node = queue.front();
        queue.pop();
        if (node.left) queue.push(node->left);
        if (node.right) queue.push(node->right);
    }
}
*/

#include <iostream>
#include <vector>
#include <queue>

#include "common/utils.hpp"

// 层序遍历
// 与基础的 BFS 不同点在于需要区分每一层的节点
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::queue<TreeNode*> treeNodeQueue;
    
    if (root != nullptr) {
        treeNodeQueue.push(root);
    }
    
    std::vector<std::vector<int>> result;
    while (!treeNodeQueue.empty())
    {
        std::vector<int> vec;
        // 需要先记录这一层有几个节点
        int size = treeNodeQueue.size();
        for (int i{}; i < size; i++) {
            TreeNode* node = treeNodeQueue.front();
            vec.push_back(node->val);
            treeNodeQueue.pop();
            if (node->left) treeNodeQueue.push(node->left);
            if (node->right) treeNodeQueue.push(node->right);
        }
        result.push_back(vec);
    }

    return result;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<std::vector<int>> res = levelOrder(commonRoot);
    std::cout << "levelOrder: \n";
    for (int i{}; i < res.size(); i++) {
        printVector(res[i]);
    }
}